#include <vector>

using namespace std;

// 被围绕的区域
// 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域
// 并将这些区域里所有的 'O' 用 'X' 填充。
// 测试链接 : https://leetcode.cn/problems/surrounded-regions/

class Solution 
{
private:
    int m, n;

    void dfs(vector<vector<char>>& board, int i, int j)
    {
        if(i == -1 || i == m || j == -1 || j == n || grid[i][j] != 'O') return;

        board[i][j] = 'A';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }

public:
    void solve(vector<vector<char>>& board) 
    {
        m = board.size(), n = board[0].size();
        // 从边界进行 FloodFill 算法，将与边界的 'O' 相连
        // 的都改成 'A'
        for(int j = 0; j < n; ++j)
        {
            if(board[0][j] == 'O') dfs(board, 0, j);
            if(board[m - 1][j] == 'O') dfs(board, m - 1, j);
        }
        for(int i = 1; i < m - 1; ++i)
        {
            if(board[i][0] == 'O') dfs(board, i, 0);
            if(board[i][n - 1] == 'O') dfs(board, i, n - 1);
        }

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == 'A') board[i][j] = 'O';
                else if(board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }
};

// 另一种 dfs 的解法
class Solution 
{
private:
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    void dfs(vector<vector<char>>& board, int i, int j)
    {
        board[i][j] = 'A';

        for(int k = 0; k < 4; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
            {
                dfs(board, x, y);
            }
        }
    }

public:
    void solve(vector<vector<char>>& board) 
    {
        m = board.size(), n = board[0].size();
        for(int j = 0; j < n; ++j)
        {
            if(board[0][j] == 'O') dfs(board, 0, j);
            if(board[m - 1][j] == 'O') dfs(board, m - 1, j);
        }
        for(int i = 1; i < m - 1; ++i)
        {
            if(board[i][0] == 'O') dfs(board, i, 0);
            if(board[i][n - 1] == 'O') dfs(board, i, n - 1);
        }

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == 'A') board[i][j] = 'O';
                else if(board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }
};

// bfs 的解法
class Solution 
{
private:
    int m, n;
    int move[5] = {-1, 0, 1, 0, -1};

    void BFS(vector<vector<char>>& board, int i, int j)
    {
        queue<int> q;
        q.emplace(i * n + j);
        board[i][j] = 'A';
        while(!q.empty())
        {
            int pos = q.front();
            q.pop();
            for(int k = 0; k < 4; ++k)
            {
                int x = pos / n + move[k];
                int y = pos % n + move[k + 1];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
                {
                    board[x][y] = 'A';
                    q.emplace(x * n + y);
                }
            }
        }
    }

public:
    void solve(vector<vector<char>>& board) 
    {
        m = board.size(), n = board[0].size();
        for(int j = 0; j < n; ++j)
        {
            if(board[0][j] == 'O') bfs(board, 0, j);
            if(board[m - 1][j] == 'O') bfs(board, m - 1, j);
        }
        for(int i = 0; i < m; ++i)
        {
            if(board[i][0] == 'O') bfs(board, i, 0);
            if(board[i][n - 1] == 'O') bfs(board, i, n - 1);
        }

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == 'A') board[i][j] = 'O';
                else if(board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }
};